Packet data radio services are becoming increasingly widespread and it is frequently the case that a number of sources are competing for the same opportunity to use an air interface resource. The unit of air interface access might be a MAC (media access control) frame for example, as it is under the rules and regulations of the GPRS-136 standard. In accordance with this standard, packet data messages are transferred on the downlink (base station to mobile station) and uplink (mobile station to base station) over the Packet Control Channel (PCCH). With a well-defined PCCH configuration and multiplexing, the GPRS-136 standard restricts the transmission over the PCCH on a slot reservation basis after an initial contention access; for each MAC frame of a given message, a slot is reserved for its transmission on the air interface.
With the many data transfer applications which may be supported by a single air interface protocol, (E-mail, ftp, web browsing, control messages transparent to the end user etc.) a fair scheduling algorithm for implementation at the base station which organizes the slot reservation process for the concurrent transactions on the uplink and the downlink is required.
While many different scheduling algorithms have been proposed for land-line packet data services, these do not translate well to the wireless environment. For example, round robin scheduling has been investigated, but this proved to result in poor performance due to its lack of consideration for transaction priority, length, and type. Many sources were severely penalized (in terms of delay) by other sources which occupied a large portion of the available limited bandwidth.
A consideration when developing any scheduling algorithm is efficiency since the algorithm needs to be executed each time an air interface unit is to be transmitted. Poor algorithm efficiency leads either to increased complexity being necessary to provide the required speed, or to delays by the scheduler itself.